package SwordForOffer.Problem33;

import java.util.Arrays;

public class PrintMinNumber {
	/*
	 * 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印出能拼接出的所有数字中的最小的一个
	 */
	public void printMin(int[] array)
	{
		int[] clone=array.clone();
		printMinNumber(clone,0,clone.length-1);
		for(int i:clone)
			System.out.print(i);
	}
	/*
	 * 核心，比较+快排
	 */
	public void printMinNumber(int[] array,int start,int end) {
		if(start<end) {
			int main_number=array[end]; //main number
			int small_cur=start;
			for (int j=start;j<end;j++) {
				if(isSmall(String.valueOf(array[j]),String.valueOf(main_number))) {
					int temp=array[j];
					array[j]=array[small_cur];
					array[small_cur]=temp;
					small_cur++;
				}
			}
			array[end]=array[small_cur];
			array[small_cur]=main_number;
			printMinNumber(array,0,small_cur-1);
			printMinNumber(array,small_cur+1,end);
		}	
	}
	private boolean isSmall(String m,String n) {
		String left=m+n;
		String right=n+m;
		boolean result=false;
		for(int i=0;i<left.length();i++) {
			if(left.charAt(i)<=right.charAt(i))
				return true;
			else
				if(left.charAt(i)>right.charAt(i))
					return false;
		}
		return result;
	}

	public void myPrintMin(int[] array) {
		if (array == null || array.length < 1){
			return;
		}
		int[] arrClone = array.clone();
		sortInOrder(arrClone,0,arrClone.length - 1);
		for (int i:arrClone){
			System.out.print(i);
		}

	}

	private void sortInOrder(int[] arrClone, int startIndex, int endIndex) {
		if (startIndex >= endIndex){
			return;
		}
		int start = startIndex;
		int end = endIndex;
		int key = arrClone[startIndex];
		while (start < end){
			while (isSmall(String.valueOf(key),String.valueOf(String.valueOf(arrClone[end])))
					&& start < end){
				end --;
			}
			arrClone[start] = arrClone[end];
			while (isSmall(String.valueOf(arrClone[start]),String.valueOf(String.valueOf(key)))
					&& start < end){
				start ++;
			}
			arrClone[end] = arrClone[start];
		}
		arrClone[startIndex] = arrClone[start];
		arrClone[start] = key;

		sortInOrder(arrClone,startIndex,start - 1);
		sortInOrder(arrClone,start + 1,endIndex);
	}
}
